# !/usr/bin/python
# -*- coding: utf-8 -*-

"""
@contact: 微信 1257309054
@file: shell.py
@time: 2022/7/25 21:30
@author: LDC
"""
'''
4、希尔排序(Shell Sort)
是插入排序的一种。也称缩小增量排序，
是直接插入排序算法的一种更高效的改进版本。
希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。
希尔排序是记录按下标的一定增量分组，对每组使用直接插入排序算法排序；
随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，
整个文件恰被分成一组，算法便终止。
'''
import random
import time


def shellSort(list1):
    # 设定步长
    step = len(list1) // 2
    while step > 0:
        for i in range(step, len(list1)):
            # 类似插入排序, 当前值与指定步长之前的值比较, 符合条件则交换位置
            while i >= step and list1[i - step] > list1[i]:
                list1[i], list1[i - step] = list1[i - step], list1[i]
                i -= step
        step = step // 2  # 步长值改为之前的二分之一


if __name__ == '__main__':
    list1 = [random.randint(1, 999) for i in range(10000)]
    list11 = list1.copy()
    start1 = time.perf_counter()
    shellSort(list1)
    end1 = time.perf_counter()
    print("希尔排序      ", end1 - start1)

    start2 = time.perf_counter()
    list4 = sorted(list11)
    end2 = time.perf_counter()
    print("函数sorted排序", end2 - start2)
    print("排序结果", list1 == list4)
